package com.cat.greedyAlgorithm;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/student-attendance-record-ii/description/
 * @create 2025/10/10 19:13
 * @since JDK17
 */

public class Solution75 {
    public int checkRecord(int n) {
        long[][] dp = new long[n][6];
        int N = ((int) (1e9 + 7));
        // dp[i][j] : 到第i天时，j = 3 * 缺情 + 迟到
        dp[0][0] = dp[0][1] = dp[0][3] = 1;
        for (int i = 1; i < n; i++) {
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % N;
            dp[i][1] = dp[i - 1][0];
            dp[i][2] = dp[i - 1][1];
            dp[i][3] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5]) % N;
            dp[i][4] = dp[i - 1][3];
            dp[i][5] = dp[i - 1][4];
        }
        long ans = 0;
        for (long num : dp[n - 1]) {
            ans = (ans + num) % N;
        }
        return ((int) ans);
    }
}
